제4장. 쇼어의 소인수분해 알고리즘

지금까지의 알고리즘(도이치-조사, 사이먼)은 양자 컴퓨터가 고전 컴퓨터보다 빠를 수 있음을 ’증명’하는 개념적 성격이 강했습니다. 1994년 피터 쇼어(Peter Shor)가 발표한 이 알고리즘은, 실질적이고 중요한 문제, 즉 큰 수의 소인수분해를 고전 컴퓨터로는 불가능한 속도(지수적-exponential-에서 다항식-polynomial- 시간으로)로 풀 수 있음을 보여주었습니다.

현재 인터넷 암호 표준(RSA)의 안전성이 “큰 수의 소인수분해는 매우 어렵다”는 가정에 기반하고 있기에, 이 알고리즘은 양자 컴퓨팅 시대를 연 가장 중요한 알고리즘으로 평가받습니다.

쇼어 알고리즘의 핵심은 3장에서 배운 양자 푸리에 변환(QFT)을 사용하여, ‘소인수분해 문제’를’주기 찾기(Period-Finding) 문제’로 변환하여 해결하는 것입니다.

1. 기본 개념 (Fundamental Concepts)

  • 문제: 소인수분해 (Factoring): 매우 큰 합성수 \(N\)이 주어졌을 때, \(N=p \times q\)를 만족하는 소수 \(p\)와 \(q\)를 찾는 문제입니다. 고전적으로는 \(N\)의 비트 수에 대해 지수적 시간이 걸립니다.

  • 1단계 (고전): 소인수분해를 주기 찾기로 변환: 쇼어 알고리즘의 첫 번째 천재성은 이 문제가 수학적으로 ’함수의 주기 찾기’와 동치임을 보인 것입니다.

    1. \(N\)과 서로소인 임의의 수 \(a < N\)를 선택합니다. (\(\text{gcd}(a, N) = 1\))
    2. 함수 \(f(x) = a^x \pmod N\) 를 정의합니다.
    3. 이 함수는 \(a^r \equiv 1 \pmod N\) 을 만족하는 최소의 주기 \(r\)을 가집니다.
    4. 만약 이 \(r\)을 찾고, \(r\)이 짝수라면, \(a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod N\)
    5. 이는 \((a^{r/2}-1)(a^{r/2}+1)\)이 \(N\)의 배수임을 의미합니다.
    6. 따라서 \(\text{gcd}(a^{r/2}-1, N)\) 또는 \(\text{gcd}(a^{r/2}+1, N)\)는 높은 확률로 \(N\)의 소인수( \(p\) 또는 \(q\) )가 됩니다.

    요약: 소인수분해(\(N\)) \(\implies\) \(f(x) = a^x \pmod N\)의 주기(\(r\)) 찾기. 고전 컴퓨터에게 어려운 것은 \(N\)을 소인수분해하는 것이고, 양자 컴퓨터에게 어려운 것은 \(r\)을 찾는 것입니다.

  • 2단계 (양자): 주기 찾기 (The Quantum Core): 고전적으로 \(r\)을 찾는 것은 \(N\)을 직접 소인수분해하는 것만큼 어렵습니다. 하지만 양자 컴퓨터는 3장에서 배운 QFT를 이용해 이 주기를 효율적으로 찾을 수 있습니다.

    1. 준비: 두 개의 레지스터, \(|x\rangle\) (입력)와 \(|y\rangle\) (출력)를 준비합니다. \(|\psi_0\rangle = |0\rangle |0\rangle\)
    2. 중첩: 입력 레지스터에 H 게이트를 적용하여 모든 \(x\)의 중첩을 만듭니다. ( \(N_q = 2^n\) ) \(|\psi_1\rangle = \left( \frac{1}{\sqrt{N_q}}\sum_{x=0}^{N_q-1} |x\rangle \right) |0\rangle\)
    3. 양자 병렬성 (모듈러 지수화): \(f(x) = a^x \pmod N\)을 계산하는 오라클 \(U_f\)를 적용합니다. 이 \(U_f\) 회로(모듈러 지수화)는 복잡하지만 다항식 시간 안에 구현 가능합니다. \(|\psi_2\rangle = U_f |\psi_1\rangle = \frac{1}{\sqrt{N_q}}\sum_{x=0}^{N_q-1} |x\rangle |a^x \pmod N\rangle\)
    4. 측정 (상태 붕괴): 출력 레지스터 \(|a^x \pmod N\rangle\)를 측정합니다.
      • 측정 결과로 어떤 값 \(k\)가 나옵니다. (예: \(k = a^{x_0} \pmod N\))
      • 이 측정으로 인해, 입력 레지스터의 상태는 \(f(x)=k\)를 만족하는 \(x\)들의 중첩 상태로 붕괴합니다. \(f(x)\)는 주기 \(r\)을 가지므로, 이 \(x\)들은 \(x_0, x_0+r, x_0+2r, \dots\) 입니다.
      • \(|\psi_3\rangle = \left( \frac{1}{\sqrt{M}}\sum_{j=0}^{M-1} |x_0 + jr\rangle \right) |k\rangle \quad\) (M은 \(N_q/r\)에 근사)
    5. QFT (주파수 추출): 이제 입력 레지스터는 완벽한 주기 \(r\)을 가진 상태가 되었습니다. 이 상태에 역 양자 푸리에 변환(QFT\(^\dagger\))을 적용합니다.
      • 주기 \(r\)을 가진 ‘시간’ 영역의 신호를 푸리에 변환하면, 주파수 \(1/r\)의 배수에서 피크(peak)가 나타납니다.
      • \(\text{QFT}^\dagger |\psi_3\rangle \implies\) 측정 결과 \(c\)는 높은 확률로 \(\frac{c}{N_q} \approx \frac{m}{r}\) ( \(m\)은 정수)을 만족하는 값이 나옵니다.
    6. 측정 (결과): 입력 레지스터를 측정하여 \(c\) 값을 얻습니다.

  • 3단계 (고전): 연분수 알고리즘 (Continued Fractions): 우리는 \(r\)을 원하지만, 양자 컴퓨터는 \(c\)를 주었습니다. 우리는 \(\frac{c}{N_q} \approx \frac{m}{r}\) 라는 근사치만 압니다. 연분수 알고리즘은 \(\frac{c}{N_q}\)라는 소수를 가장 잘 근사하는 기약분수 \(\frac{m}{r}\)을 찾아내는 매우 효율적인 고전 알고리즘입니다.

    • 이 알고리즘을 통해 \(r\)을 (높은 확률로) 찾아냅니다.

2. 기호 및 핵심 관계식

  • 문제: \(N=pq\)
  • 고전적 환원: \(\text{gcd}(a, N)=1\)인 \(a\)를 선택, \(f(x) = a^x \pmod N\)의 주기 \(r\)을 찾는다.
  • 주기 조건: \(a^r \equiv 1 \pmod N\)
  • 인수: \(\text{gcd}(a^{r/2} \pm 1, N)\)
  • 양자 오라클: \(U_f |x\rangle |y\rangle = |x\rangle |y \oplus (a^x \pmod N)\rangle\) (또는 \(|x\rangle |a^x \pmod N\rangle\))
  • 핵심 상태 붕괴: \(\frac{1}{\sqrt{N_q}}\sum_{x} |x\rangle |a^x \pmod N\rangle \xrightarrow{\text{Measure } |k\rangle} \frac{1}{\sqrt{M}}\sum_{j} |x_0 + jr\rangle\)
  • QFT\(^\dagger\) 결과: \(\text{QFT}^\dagger (\sum_j |x_0 + jr\rangle) \implies\) 측정값 \(c\)는 \(c \approx m \frac{N_q}{r}\) ( \(m \in \{0, 1, \dots, r-1\}\) )
  • 고전적 후처리: \(\frac{c}{N_q} \approx \frac{m}{r} \xrightarrow{\text{Continued Fractions}} r\)

3. 손쉬운 예제: N=15 소인수분해 (가상 시뮬레이션)

  • 문제: \(N=15\)를 소인수분해하시오. (고전적으로 답은 3, 5임을 압니다.)

  • 1단계 (고전):

    1. \(a=7\)을 임의로 선택합니다. (\(\text{gcd}(7, 15)=1\), OK)
    2. 우리의 목표: \(f(x) = 7^x \pmod{15}\)의 주기 \(r\)을 찾습니다.
    • (미리 계산: \(7^0=1, 7^1=7, 7^2=49\equiv 4, 7^3=28\equiv 13, 7^4=91\equiv 1\). 주기는 \(r=4\)입니다. 양자 컴퓨터가 이 ’4’를 찾아야 합니다.)

  • 2단계 (양자):

    1. 준비: \(N=15\)를 다루기 위해 \(n=4\)비트 (\(N_q=16\)) 입력 레지스터를 쓴다고 가정합니다. (실제로는 \(N^2\) 근처, 즉 8비트가 필요하지만, 개념 설명을 위해 \(n=4\)로 단순화합니다.)
    2. 중첩: \(|\psi_1\rangle = \frac{1}{\sqrt{16}}\sum_{x=0}^{15} |x\rangle |0\rangle\)
    3. 오라클: \(U_f\)가 \(f(x)=7^x \pmod{15}\)를 병렬 계산합니다. \(|\psi_2\rangle = \frac{1}{4} \Big( |0\rangle|1\rangle + |1\rangle|7\rangle + |2\rangle|4\rangle + |3\rangle|13\rangle + |4\rangle|1\rangle + |5\rangle|7\rangle + \dots \Big)\)
    4. 측정 (붕괴): 출력 레지스터를 측정합니다. 운 좋게 \(k=1\)이 측정되었다고 가정합시다.
    5. 입력 레지스터는 \(f(x)=1\)인 \(x\)들, 즉 \(x=0, 4, 8, 12\)의 중첩 상태로 붕괴합니다. \(|\psi_3\rangle = \frac{1}{\sqrt{4}}(|0\rangle + |4\rangle + |8\rangle + |12\rangle)\)
    6. QFT\(^\dagger\) (주파수 추출): 이 주기 \(r=4\) 상태에 \(\text{QFT}_{16}^\dagger\)를 적용합니다.
      • 이론적으로, 이 변환은 \(m \cdot (N_q/r) = m \cdot (16/4) = 4m\) 인 상태들, 즉 \(|0\rangle, |4\rangle, |8\rangle, |12\rangle\)의 균등한 중첩을 만듭니다.

  • 💡 상세 설명 (QFT가 주기를 찾는 원리)

    \(|\psi_3\rangle\) 상태는 “주기 4짜리 빗살무늬 파동”입니다. 3장에서 QFT가 시간(위치) 영역을 주파수 영역으로 바꾼다고 했습니다.

    • \(\text{QFT}(\text{주기 } r \text{ 파동}) = \text{주기 } N_q/r \text{ 파동}\)

    \(r=4, N_q=16\)이므로, \(\text{QFT}^\dagger\)는 주기가 \(16/4 = 4\)인 상태를 만듭니다. 즉, 측정 결과 \(c\)는 \(0, 4, 8, 12\) 중 하나가 됩니다. (모든 \(x\)에 대해 \(e^{-2\pi i xc / 16}\)의 보강 간섭이 일어나는 \(c\) 값들입니다.)

  • 3단계 (고전):

    1. 측정: 입력 레지스터를 측정하여 \(c=8\)을 얻었다고 합시다. (0은 정보가 없으므로 다시 시도)
    2. 연분수: 우리는 \(\frac{c}{N_q} = \frac{8}{16} = \frac{1}{2}\)을 얻었습니다.
    3. \(\frac{m}{r} = \frac{1}{2}\) 입니다. \(m\)은 \(r\)보다 작은 정수이므로, \(m=1, r=2\) 또는 \(m=2, r=4\) 등이 가능합니다. \(a^{r/2} \not\equiv -1 \pmod N\)인지 확인하며 \(r=4\)를 선택합니다. (실제로는 \(c=4\) (\(m/r=1/4 \to r=4\)) 또는 \(c=12\) (\(m/r=3/4 \to r=4\))가 나올 확률이 더 높습니다.)
    4. \(r=4\)를 찾았다고 가정합니다.

  • 최종 계산 (고전):

    • \(r=4\) (짝수), \(a=7\).
    • \(\text{gcd}(a^{r/2} - 1, N) = \text{gcd}(7^2 - 1, 15) = \text{gcd}(48, 15) = \mathbf{3}\)
    • \(\text{gcd}(a^{r/2} + 1, N) = \text{gcd}(7^2 + 1, 15) = \text{gcd}(50, 15) = \mathbf{5}\)
    • \(N=15\)의 소인수 3과 5를 성공적으로 찾았습니다.

4. 연습문제

  1. 고전적 환원: \(N=21\)을 소인수분해하기 위해 \(a=4\)를 선택했습니다. \(f(x) = 4^x \pmod{21}\)의 주기 \(r\)을 손으로 계산하고, \(\text{gcd}(a^{r/2} \pm 1, 21)\)를 통해 소인수를 찾아보십시오.
  2. QFT 결과 예측: \(N=15\) ( \(r=4\) ) 예제에서, 8비트(\(N_q=256\)) 레지스터를 사용했다고 가정합니다. QFT\(^\dagger\) 측정 후 \(c\) 값으로 어떤 값들이 주로 측정될지 예측하십시오.
  3. 알고리즘 실패: \(N=15\)에 \(a=14\)를 선택했습니다. 주기 \(r\)은 얼마이며, 왜 이 \(r\) 값으로는 소인수를 찾을 수 없는지 설명하십시오.
  4. 효율성 비교: \(n=1000\) 비트 크기의 수(\(N \approx 10^{300}\))를 소인수분해할 때, 고전 컴퓨터(지수적 \(O(e^{n^{1/3}})\))와 쇼어 알고리즘(다항식 \(O(n^3)\))의 차이를 정성적으로 설명하십시오.

5. 해설

  1. \(4^1=4\), \(4^2=16\), \(4^3=64=3\cdot 21 + 1 \equiv 1\). 주기 \(r=3\)입니다. \(r=3\)은 홀수이므로, \(r/2\)가 정수가 아닙니다. \(\text{gcd}(a^{r/2} \pm 1, N)\) 계산을 수행할 수 없습니다. 결론: \(a=4\)는 ‘나쁜’ 선택이었습니다. 알고리즘 1단계로 돌아가 다른 \(a\)(예: \(a=2\))를 다시 선택해야 합니다.
  2. \(N_q = 256, r=4\). 측정값 \(c\)는 \(c \approx m \cdot (N_q/r) = m \cdot (256/4) = 64m\) 근처의 값들입니다. 주로 \(c=0, 64, 128, 192\) (및 그 근처의 값들)이 측정될 것입니다. ( \(c=0\)은 유용한 정보를 주지 않습니다.)
  3. \(a=14 \equiv -1 \pmod{15}\). \(14^1 \equiv -1 \equiv 14 \pmod{15}\) \(14^2 \equiv (-1)^2 \equiv 1 \pmod{15}\). 주기 \(r=2\)입니다. \(r=2\)는 짝수이므로 다음 단계로 갑니다. \(\text{gcd}(a^{r/2} - 1, N) = \text{gcd}(14^{2/2} - 1, 15) = \text{gcd}(14-1, 15) = \text{gcd}(13, 15) = 1\). (실패) \(\text{gcd}(a^{r/2} + 1, N) = \text{gcd}(14^{2/2} + 1, 15) = \text{gcd}(14+1, 15) = \text{gcd}(15, 15) = 15\). (실패) 이는 \(a^{r/2} \equiv -1 \pmod N\) (즉, \(14 \equiv -1 \pmod{15}\)) 이라는 ‘사소한’ 경우에 해당하기 때문입니다. 이 경우에도 소인수를 찾지 못하며, 1단계로 돌아가 \(a\)를 다시 선택해야 합니다.
  4. \(n=1000\)일 때, 고전 컴퓨터는 \(O(e^{1000^{1/3}}) \approx O(e^{10})\) (약 22,000)이 아니라, \(O(e^{c n^{1/3}(\log n)^{2/3}})\)으로 훨씬 큽니다. 이는 사실상 우주의 나이보다 긴 시간이 걸려 계산이 불가능합니다. 반면 양자 컴퓨터는 \(O(n^3) = O(1000^3) = 10^9\) (10억) 정도의 연산만 필요합니다. 이는 현대 슈퍼컴퓨터로도 수 초~수 분 안에 처리할 수 있는 계산량입니다. 즉, ’불가능’한 문제를 ’가능’한 문제로 바꿉니다.